package com.lcm.oj.lanqiao.year2021.zhenti;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author Coder-lcm
 * @date 2021/5/6
 *
 *  分解因数 + dfs深度遍历（回溯算法）
 */
public class Td_货物摆放 {
    static Deque<Long> temp = new LinkedList<>();
    static List<Long> yinShu = new ArrayList<>();
    static long count = 0;
    static long n = 2021041820210418L;

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println((long) Math.sqrt(n));
        // 获取因数
        for (long i = 1, end = (long) Math.sqrt(n); i <= end; i++) {
            if (n % i == 0) {
                yinShu.add(i);
                yinShu.add(n / i);
            }
        }

        //因数去重
        yinShu = yinShu.stream().distinct().collect(Collectors.toList());
        System.out.println("因数总个数：" + yinShu.size());
        dfs(0,1);
        System.out.println(count);
        System.out.println("耗时：" + (System.currentTimeMillis()-start));
    }


    static void dfs(int be, long now){
        if (temp.size() == 3) {
            if (now == n) {
                Iterator<Long> iterator = temp.iterator();
                while (iterator.hasNext()){
                    System.out.print(iterator.next() + "--");
                }
                System.out.println();
                count++;
            }
            return;
        }

        for (int i = be; i < yinShu.size(); i++) {
            //做选择
            temp.addLast(yinShu.get(i));
            dfs(be, now * yinShu.get(i));
            // 撤销选择
            temp.removeLast();
        }
    }
}
